package dp;

import java.util.Arrays;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 获取生成数组中的最大值1646.java
 * @Description https://leetcode-cn.com/problems/get-maximum-in-generated-array/
 * @createTime 2021年12月07日 20:42:00
 *
 * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
 *
 * nums[0] = 0
 * nums[1] = 1
 * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
 * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
 *
 */
public class 获取生成数组中的最大值1646 {
	public int getMaximumGenerated(int n) {
		if (n < 2) {
			return n;
		}
		/**
		 * 定义备忘录 dp[i]表示位置i的值
		 */
		int[] dp = new int[n + 1];

		//初始抓
		dp[0] = 0;
		dp[1] = 1;
		/**
		 * 状态转移
		 */
		int max = 0;
		for (int i = 2; i <= n; i++) {
			dp[i] = i % 2 == 0 ? dp[i / 2] : dp[i / 2] + dp[i / 2 + 1];
			max = Math.max(max, dp[i]);
		}
		return max;
	}
}
